package l.l.w.CodingInterviews;

import org.junit.Test;

import java.util.ArrayList;

/**
 * Created by llw on 2018/3/2.
 */
public class LearnList {

    /**
     * 从无头链表中删除指定节点
     * 题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]
     * 分析：
     *      本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，
     *      即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。
     * @param listNode
     */
    public void deleteNode(ListNode listNode){
        if(listNode == null) return;
        if(listNode.next == null) return;
        ListNode next = listNode.next;
        listNode.val = next.val;
        listNode.next = next.next;
    }
    @Test
    public void testDeleteNode(){
        ListNode head = new ListNode(0);
        ListNode listNode = head.add(1).add(2);
        listNode.add(3).add(4).add(5);
        new LearnList().deleteNode(listNode);
        ListNode cur = head;
        while(cur!=null){
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    /**
     * 2. 单链表的转置
     * 题目描述：输入一个单向链表，输出逆序反转后的链表
     * 分析：
     *      链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，
     *      用三个临时指针 pre、head、next 在链表上循环一遍即可。
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head){
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode pre = head;
        ListNode cur = head.next;
        head.next = null;   //这个地方很重要，head.next必须为null，否则的话head.next与下一个元素互相next指向，会形成一个环！！！！
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 从尾到头打印链表
     *  题目描述:
     *      输入一个链表，从尾到头打印链表每个节点的值。
     *  分析：
     *      如果可以改变原来的链表结果，则可以翻转之后再输出。
     *      如果不可以改变编表结构：
     *          可以使用库函数，
     * @param listNode
     * @return
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList result = new ArrayList<Integer>();
        getNext(listNode,result);
        return result;
    }
    private void getNext(ListNode node, ArrayList<Integer> list){
        if(node == null) return;
        getNext(node.next,list);
        list.add(node.val);
    }
    @Test
    public void test2(){
        ListNode head = new ListNode(0);
        ListNode listNode = head.add(1).add(2);
        listNode.add(3).add(4).add(5);
        System.out.println("1");
        ListNode p = listNode.next.next.next;
        p=null;
        System.out.println(listNode.next.next);
    }


    /**
     * 给定链表的头结点和节点p，从链表中删除节点p、
     *      时间复杂度为O(1)
     *      如果head和p为null，则直接返回（输入数据校验）
     *      如果删除的是头结点，则直接head= head.next即可
     *      如果待删除的节点不是尾节点，则直接将p.next的值复制给p，然后删除p.next即可。
     *      如果待删除的节点为尾节点，则需要从头遍历，找到p的前驱节点，然后删除。
     * @param head
     * @param p
     */
    public void deleteNode(ListNode head, ListNode p){
        if(head == null || p == null) return;
        if(head == p) {
            head = head.next;
            return;
        }
        if(p.next != null){
            p.val = p.next.val;
            p.next = p.next.next;
        }else{
            ListNode cur = head;
            while(cur.next != p){
                cur = cur.next;
            }
            cur.next = null;
        }
    }
}
class ListNode {
    int val;
    ListNode next;
    public ListNode(int val){
        this.val = val;
    }
    public ListNode add(int val){
        ListNode listNode = new ListNode(val);
        next = listNode;
        return listNode;
    }
}
